package org.feit.findword.trie;


import java.io.InputStream;
import java.io.BufferedInputStream;
import java.io.IOException;

/**
 * This class reads a compressed trie file and deserializes it to a Trie. It has
 * a lower memory footprint than the regular Trie, and supports the ability to
 * prune the Trie while it is being read.
 * 
 * This is the class that should be used on mobile devices.
 */
public class CompressedTrieMk extends TrieMk {

	private int nodesRead;
	private int nodesSaved;

	private static long[] FOLLOW_MASKS = { 0x7fffffffL, 0x7fffffffL,
			0x7fffffffL, 0x7fffffffL, 0x7fffffffL, 0x7fffffffL, 0x7fffffffL,
			0x7fffffffL, 0x7fffffffL, 0x7fffffffL, 0x7fffffffL, 0x7fffffffL,
			0x7fffffffL, 0x7fffffffL, 0x7fffffffL, 0x7fffffffL, 0x7fffffffL,
			0x7fffffffL, 0x7fffffffL, 0x7fffffffL, 0x7fffffffL, 0x7fffffffL,
			0x7fffffffL, 0x7fffffffL, 0x7fffffffL, 0x7fffffffL, 0x7fffffffL,
			0x7fffffffL, 0x7fffffffL, 0x7fffffffL, 0x7fffffffL };

	public CompressedTrieMk(InputStream input) throws IOException {
		this(input, 0x7fffffffL);
	}

	public CompressedTrieMk(InputStream input, long mask) throws IOException {
		this(input, mask, FOLLOW_MASKS);
	}

	public CompressedTrieMk(InputStream input, long mask, long[] neighborMasks)
			throws IOException {
		super();
		nodesRead = 0;
		nodesSaved = 0;
		mask |= WORD_BIT;
		root = readTrie(new BufferedInputStream(input, 8192), mask,
				neighborMasks, -1, true, true);
	}

	private TrieMk.TrieNode readTrie(InputStream input, long mask,
			long[] neighborMasks, int value, boolean store, boolean isRoot)
			throws IOException {
		nodesRead++;
		long firstByte = (long) input.read() << 32;

		if ((firstByte & LEAF_BIT) != 0) {
			// This node is a tail.
			if (store) {
				if ((firstByte & mask) != 0) {
					return EMPTY_LEAF.processWordBits(firstByte & mask);
				}
			}
			return null;
		}

		long cBits = firstByte;
		cBits |= input.read() << 24;
		cBits |= input.read() << 16;
		cBits |= input.read() << 8;
		cBits |= input.read();

		int nextBits = input.read() << 16;
		nextBits |= input.read() << 8;
		nextBits |= input.read();

		if (!store) {
			while (nextBits > 0) {
				nextBits -= input.skip(nextBits);
			}
			return null;
		}

		long maskedBits = cBits & mask;
		if (value > -1) {
			maskedBits &= WORD_BIT | neighborMasks[value];
		}

		if (maskedBits != 0) {
			TrieNode ret = null;
			int childNumber = 0;
			for (int i = 0; i < LETTERS_COUNT; i++) {
				if ((maskedBits & (1 << i)) != 0) {
					TrieNode child = readTrie(input, mask, neighborMasks, i,
							true, false);
					if (child != null) {
						if (ret == null) {
							ret = new CompressedTrieNode(maskedBits);
							nodesSaved++;
						}
						ret.children[childNumber] = child;
						childNumber++;
					} else {
						maskedBits ^= (1 << i);
					}
				} else if ((cBits & (1 << i)) != 0) {
					readTrie(input, mask, null, -1, false, false);
				}
			}
			if (ret != null) {
				// node has valid children
				ret.childBits = maskedBits;
				return ret;
			} else if ((maskedBits & WORD_BIT) != 0) {
				// node has no valid children but is a word.
				return EMPTY_LEAF.processWordBits(cBits & WORD_BIT);
			}
			return null;
		}
		for (cBits &= LETTER_MASK; cBits != 0; cBits >>= 1) {
			if ((cBits & 1) != 0) {
				readTrie(input, mask, null, -1, false, false);
			}
		}
		if ((cBits & WORD_BIT) != 0) {
			return EMPTY_LEAF.processWordBits(cBits & WORD_BIT);
		}
		return null;
	}

	/**
	 * The CompressedTrieNode is like a normal TrieNode, but only allocates a
	 * large enough Array to store the number of children that it is known to
	 * have.
	 */
	protected class CompressedTrieNode extends TrieMk.TrieNode {
		public CompressedTrieNode(long cBits) {
			childBits = cBits;
			children = new TrieNode[countBits(cBits)];
		}

		protected TrieNode childAt(int index) {
			TrieNode ret = null;
			int j = 0;
			for (int i = 0; i <= index; i++) {
				if ((childBits & (1 << i)) != 0) {
					ret = children[j];
					j++;
				} else {
					ret = null;
				}
			}
			return ret;
		}
	}

	static void traverseTree(TrieNode t, StringBuilder sb) {
		if (t.isTail()) {
			System.out.println(sb.toString());
			return;
		} else {
			if (t.isWord()) {
				System.out.println(sb.toString());
			}
		}
		int child = 0;
		for (int i = 0; i < LETTERS_COUNT; i++) {
			if ((t.childBits & (1 << i)) != 0) {
				char c = LettersMap.itouc(i);
				sb.append(c);
				traverseTree(t.childAt(i), sb);
				sb.deleteCharAt(sb.length() - 1);
				child++;
			}
		}
	}

}
